package basic.basic_class02;

/**
 * author： Code_Yang
 */
public class Test {

    public static String answer(String str) {
        if(str == null || str.equals("") || str.length() == 1) return str;
        if(str.length() == 2) return str.charAt(0) == str.charAt(1) ? str.substring(1) : str;
        int[] next = getNext(str.toCharArray());
        return str.substring(next[str.length()]);
    }

    private static int[] getNext(char[] sm) {
        int[] res = new int[sm.length + 1];
        res[0] = -1;
        res[1] = 0;
        int pos = 2;
        int cn = 0;
        while (pos <= sm.length) {
            if (sm[pos - 1] == sm[cn]) {
                res[pos++] = ++cn;
            } else if (cn > 0) {
                cn = res[cn];
            } else {
                res[pos++] = 0;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        String test1 = "a";
        System.out.println(answer(test1));

        String test2 = "aa";
        System.out.println(answer(test2));

        String test3 = "ab";
        System.out.println(answer(test3));

        String test4 = "abcdabcd";
        System.out.println(answer(test4));

        String test5 = "abracadabra";
        System.out.println(answer(test5));
    }
}
